package com.leetcode.binary_search;

/**
 * @author Dennis Li
 * @date 2020/7/24 18:47
 */
public class SearchRange_34 {

    public int[] searchRange(int[] nums, int target) {
        int index = binarySearch(nums, target, 0, nums.length - 1);
        if (nums.length == 0 || target != nums[index]) return new int[]{-1, -1};
        if (nums.length == 1) return new int[]{index, index};
        int i = index, j = index;
        for (; i >= 0; i--) {
            if (nums[i] != nums[index]) break;
        }
        for (; j < nums.length; j++) {
            if (nums[j] != nums[index]) break;
        }
        return new int[]{i + 1, j - 1};
    }

    private int binarySearch(int[] nums, int target, int i, int j) {
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] > target) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                j = mid;
                break;
            }
        }
        return Math.max(j, 0);
    }

    public int[] searchRange2(int[] nums, int target) {
        int first = findFirst(nums, target);
        // 找比target大的第一个位置，再往前移动一位
        int last = findFirst(nums, target + 1) - 1;
        // target比nums的最大值还大，或者不在nums中，返回-1
        if (first == nums.length || nums[first] != target) {
            return new int[]{-1, -1};
        } else {
            // 用max是为了防止+1的值不存在，或恰好在比first大一位的地方
            return new int[]{first, Math.max(first, last)};
        }
    }

    // 二分查找到第一次出现值的模板
    // 背诵，当需要返回序号值的时候的二分写法
    private int findFirst(int[] nums, int target) {
        //h初始值为nums.length
        int l = 0, h = nums.length; // 注意 h 的初始值
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] >= target) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }


    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = {1};
            int target = 0;
            System.out.println(solution.searchRange(nums, target));
        }

        public int[] searchRange(int[] nums, int target) {
            if (nums.length == 0) return new int[]{-1, -1};
            if (nums.length == 1) return nums[0] == target ? new int[]{0, 0} : new int[]{-1, -1};
            int[] res = new int[2];
            res[0] = searchFirstIndex(nums, target);
            res[1] = searchLastIndex(nums, target);
            return res;
        }

        private int searchFirstIndex(int[] nums, int target) {
            int i = 0, j = nums.length;
            while (i < j) {
                int mid = i + (j - i) / 2;
                if (nums[mid] >= target) {
                    j = mid;
                } else if (nums[mid] < target) {
                    i = mid + 1;
                }
            }
            return i >= nums.length || nums[i] != target ? -1 : i;
        }

        private int searchLastIndex(int[] nums, int target) {
            int i = 0, j = nums.length;
            while (i < j) {
                int mid = i + (j - i) / 2;
                if (nums[mid] <= target) {
                    i = mid + 1;
                } else if (nums[mid] > target) {
                    j = mid;
                }
            }
            return i == 0 || i >= nums.length || nums[i - 1] != target ? -1 : i - 1;
        }
    }

}
